package demo10;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-26
 * Time: 15:53
 */
public class TestMaxCover {

    public static int maxCover1(int[][] m){

        PriorityQueue<Integer> Pq = new PriorityQueue<>();

        //先对每个线段排成有序
        Arrays.sort(m,(a,b)->((a[0] - b[0])));
        int max = 0;
        for(int[] line : m){
            while(!Pq.isEmpty()&&Pq.peek()<=line[0]){
                Pq.poll();
            }
            Pq.add(line[1]);
            max = Math.max(max,Pq.size());
        }
        return max;
    }

    public static int maxCover(int[][] line){

        //求出所有线段的最大值和最小值
        int max = line[0][0];
        int min = line[0][0];

        for(int i =0;i< line.length;++i){
            max = Math.max(max,line[i][1]);
            min = Math.min(min,line[i][0]);

        }
        //对于每一个.5,遍历每一个线段经过.5的数量,最终最大的就是最大重合线段数量
        int cover = 0;
        for(double p = min+0.5;p< max;p++){
            int cur = 0;
            for(int i =0;i< line.length;++i){
                if(p>line[i][0]&&p<line[i][1]){
                    ++cur;
                }
            }
            cover = Math.max(cover,cur);
        }

        return cover;
    }


    public static void main(String[] args) {


    }


}
